/*
 * divsufsort.c for libdivsufsort-lite
 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

/*- Compiler specifics -*/
#ifdef __clang__
#pragma clang diagnostic ignored "-Wshorten-64-to-32"
#endif

#if defined(_MSC_VER)
#pragma warning(disable : 4244)
#pragma warning(disable : 4127) /* C4127 : Condition expression is constant */
#endif

/*- Dependencies -*/
#include "divsufsort.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

/*- Constants -*/
#if defined(INLINE)
#undef INLINE
#endif
#if !defined(INLINE)
#define INLINE __inline
#endif
#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1)
#undef ALPHABET_SIZE
#endif
#if !defined(ALPHABET_SIZE)
#define ALPHABET_SIZE (256)
#endif
#define BUCKET_A_SIZE (ALPHABET_SIZE)
#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)
#if defined(SS_INSERTIONSORT_THRESHOLD)
#if SS_INSERTIONSORT_THRESHOLD < 1
#undef SS_INSERTIONSORT_THRESHOLD
#define SS_INSERTIONSORT_THRESHOLD (1)
#endif
#else
#define SS_INSERTIONSORT_THRESHOLD (8)
#endif
#if defined(SS_BLOCKSIZE)
#if SS_BLOCKSIZE < 0
#undef SS_BLOCKSIZE
#define SS_BLOCKSIZE (0)
#elif 32768 <= SS_BLOCKSIZE
#undef SS_BLOCKSIZE
#define SS_BLOCKSIZE (32767)
#endif
#else
#define SS_BLOCKSIZE (1024)
#endif
/* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */
#if SS_BLOCKSIZE == 0
#define SS_MISORT_STACKSIZE (96)
#elif SS_BLOCKSIZE <= 4096
#define SS_MISORT_STACKSIZE (16)
#else
#define SS_MISORT_STACKSIZE (24)
#endif
#define SS_SMERGE_STACKSIZE (32)
#define TR_INSERTIONSORT_THRESHOLD (8)
#define TR_STACKSIZE (64)

/*- Macros -*/
#ifndef SWAP
#define SWAP(_a, _b) \
    do {             \
        t = (_a);    \
        (_a) = (_b); \
        (_b) = t;    \
    } while (0)
#endif /* SWAP */
#ifndef MIN
#define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
#endif /* MIN */
#ifndef MAX
#define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b))
#endif /* MAX */
#define STACK_PUSH(_a, _b, _c, _d)                                                                    \
    do {                                                                                              \
        assert(ssize < STACK_SIZE);                                                                   \
        stack[ssize].a = (_a), stack[ssize].b = (_b), stack[ssize].c = (_c), stack[ssize++].d = (_d); \
    } while (0)
#define STACK_PUSH5(_a, _b, _c, _d, _e)                                                             \
    do {                                                                                            \
        assert(ssize < STACK_SIZE);                                                                 \
        stack[ssize].a = (_a), stack[ssize].b = (_b), stack[ssize].c = (_c), stack[ssize].d = (_d), \
        stack[ssize++].e = (_e);                                                                    \
    } while (0)
#define STACK_POP(_a, _b, _c, _d)                                                                     \
    do {                                                                                              \
        assert(0 <= ssize);                                                                           \
        if (ssize == 0) {                                                                             \
            return;                                                                                   \
        }                                                                                             \
        (_a) = stack[--ssize].a, (_b) = stack[ssize].b, (_c) = stack[ssize].c, (_d) = stack[ssize].d; \
    } while (0)
#define STACK_POP5(_a, _b, _c, _d, _e)                                                                \
    do {                                                                                              \
        assert(0 <= ssize);                                                                           \
        if (ssize == 0) {                                                                             \
            return;                                                                                   \
        }                                                                                             \
        (_a) = stack[--ssize].a, (_b) = stack[ssize].b, (_c) = stack[ssize].c, (_d) = stack[ssize].d, \
        (_e) = stack[ssize].e;                                                                        \
    } while (0)
#define BUCKET_A(_c0) bucket_A[(_c0)]
#if ALPHABET_SIZE == 256
#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)])
#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)])
#else
#define BUCKET_B(_c0, _c1) (bucket_B[(_c1)*ALPHABET_SIZE + (_c0)])
#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0)*ALPHABET_SIZE + (_c1)])
#endif

/*- Private Functions -*/

static const int lg_table[256] = {
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
    5,  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6,  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6,  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7,  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7,  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7,  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};

#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)

static INLINE int ss_ilg(int n) {
#if SS_BLOCKSIZE == 0
    return (n & 0xffff0000) ? ((n & 0xff000000) ? 24 + lg_table[(n >> 24) & 0xff] : 16 + lg_table[(n >> 16) & 0xff])
                            : ((n & 0x0000ff00) ? 8 + lg_table[(n >> 8) & 0xff] : 0 + lg_table[(n >> 0) & 0xff]);
#elif SS_BLOCKSIZE < 256
    return lg_table[n];
#else
    return (n & 0xff00) ? 8 + lg_table[(n >> 8) & 0xff] : 0 + lg_table[(n >> 0) & 0xff];
#endif
}

#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */

#if SS_BLOCKSIZE != 0

static const int sqq_table[256] = {
    0,   16,  22,  27,  32,  35,  39,  42,  45,  48,  50,  53,  55,  57,  59,  61,  64,  65,  67,  69,  71,  73,
    75,  76,  78,  80,  81,  83,  84,  86,  87,  89,  90,  91,  93,  94,  96,  97,  98,  99,  101, 102, 103, 104,
    106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 128,
    129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145, 146, 147, 148, 149,
    150, 150, 151, 152, 153, 154, 155, 155, 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167,
    167, 168, 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180, 181, 181, 182, 183,
    183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
    198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211,
    212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223, 224, 224,
    225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236,
    237, 237, 238, 238, 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, 247, 248,
    248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255};

static INLINE int ss_isqrt(int x) {
    int y, e;

    if (x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) {
        return SS_BLOCKSIZE;
    }
    e = (x & 0xffff0000) ? ((x & 0xff000000) ? 24 + lg_table[(x >> 24) & 0xff] : 16 + lg_table[(x >> 16) & 0xff])
                         : ((x & 0x0000ff00) ? 8 + lg_table[(x >> 8) & 0xff] : 0 + lg_table[(x >> 0) & 0xff]);

    if (e >= 16) {
        y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7);
        if (e >= 24) {
            y = (y + 1 + x / y) >> 1;
        }
        y = (y + 1 + x / y) >> 1;
    } else if (e >= 8) {
        y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1;
    } else {
        return sqq_table[x] >> 4;
    }

    return (x < (y * y)) ? y - 1 : y;
}

#endif /* SS_BLOCKSIZE != 0 */

/*---------------------------------------------------------------------------*/

/* Compares two suffixes. */
static INLINE int ss_compare(const unsigned char* T, const int* p1, const int* p2, int depth) {
    const unsigned char *U1, *U2, *U1n, *U2n;

    for (U1 = T + depth + *p1, U2 = T + depth + *p2, U1n = T + *(p1 + 1) + 2, U2n = T + *(p2 + 1) + 2;
         (U1 < U1n) && (U2 < U2n) && (*U1 == *U2);
         ++U1, ++U2) {
    }

    return U1 < U1n ? (U2 < U2n ? *U1 - *U2 : 1) : (U2 < U2n ? -1 : 0);
}

/*---------------------------------------------------------------------------*/

#if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1)

/* Insertionsort for small size groups */
static void ss_insertionsort(const unsigned char* T, const int* PA, int* first, int* last, int depth) {
    int *i, *j;
    int t;
    int r;

    for (i = last - 2; first <= i; --i) {
        for (t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
            do {
                *(j - 1) = *j;
            } while ((++j < last) && (*j < 0));
            if (last <= j) {
                break;
            }
        }
        if (r == 0) {
            *j = ~*j;
        }
        *(j - 1) = t;
    }
}

#endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */

/*---------------------------------------------------------------------------*/

#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)

static INLINE void ss_fixdown(const unsigned char* Td, const int* PA, int* SA, int i, int size) {
    int j, k;
    int v;
    int c, d, e;

    for (v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
        d = Td[PA[SA[k = j++]]];
        if (d < (e = Td[PA[SA[j]]])) {
            k = j;
            d = e;
        }
        if (d <= c) {
            break;
        }
    }
    SA[i] = v;
}

/* Simple top-down heapsort. */
static void ss_heapsort(const unsigned char* Td, const int* PA, int* SA, int size) {
    int i, m;
    int t;

    m = size;
    if ((size % 2) == 0) {
        m--;
        if (Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) {
            SWAP(SA[m], SA[m / 2]);
        }
    }

    for (i = m / 2 - 1; 0 <= i; --i) {
        ss_fixdown(Td, PA, SA, i, m);
    }
    if ((size % 2) == 0) {
        SWAP(SA[0], SA[m]);
        ss_fixdown(Td, PA, SA, 0, m);
    }
    for (i = m - 1; 0 < i; --i) {
        t = SA[0], SA[0] = SA[i];
        ss_fixdown(Td, PA, SA, 0, i);
        SA[i] = t;
    }
}

/*---------------------------------------------------------------------------*/

/* Returns the median of three elements. */
static INLINE int* ss_median3(const unsigned char* Td, const int* PA, int* v1, int* v2, int* v3) {
    int* t;
    if (Td[PA[*v1]] > Td[PA[*v2]]) {
        SWAP(v1, v2);
    }
    if (Td[PA[*v2]] > Td[PA[*v3]]) {
        if (Td[PA[*v1]] > Td[PA[*v3]]) {
            return v1;
        } else {
            return v3;
        }
    }
    return v2;
}

/* Returns the median of five elements. */
static INLINE int* ss_median5(const unsigned char* Td, const int* PA, int* v1, int* v2, int* v3, int* v4, int* v5) {
    int* t;
    if (Td[PA[*v2]] > Td[PA[*v3]]) {
        SWAP(v2, v3);
    }
    if (Td[PA[*v4]] > Td[PA[*v5]]) {
        SWAP(v4, v5);
    }
    if (Td[PA[*v2]] > Td[PA[*v4]]) {
        SWAP(v2, v4);
        SWAP(v3, v5);
    }
    if (Td[PA[*v1]] > Td[PA[*v3]]) {
        SWAP(v1, v3);
    }
    if (Td[PA[*v1]] > Td[PA[*v4]]) {
        SWAP(v1, v4);
        SWAP(v3, v5);
    }
    if (Td[PA[*v3]] > Td[PA[*v4]]) {
        return v4;
    }
    return v3;
}

/* Returns the pivot element. */
static INLINE int* ss_pivot(const unsigned char* Td, const int* PA, int* first, int* last) {
    int* middle;
    int t;

    t = last - first;
    middle = first + t / 2;

    if (t <= 512) {
        if (t <= 32) {
            return ss_median3(Td, PA, first, middle, last - 1);
        } else {
            t >>= 2;
            return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
        }
    }
    t >>= 3;
    first = ss_median3(Td, PA, first, first + t, first + (t << 1));
    middle = ss_median3(Td, PA, middle - t, middle, middle + t);
    last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
    return ss_median3(Td, PA, first, middle, last);
}

/*---------------------------------------------------------------------------*/

/* Binary partition for substrings. */
static INLINE int* ss_partition(const int* PA, int* first, int* last, int depth) {
    int *a, *b;
    int t;
    for (a = first - 1, b = last;;) {
        for (; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) {
            *a = ~*a;
        }
        for (; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) {
        }
        if (b <= a) {
            break;
        }
        t = ~*b;
        *b = *a;
        *a = t;
    }
    if (first < a) {
        *first = ~*first;
    }
    return a;
}

/* Multikey introsort for medium size groups. */
static void ss_mintrosort(const unsigned char* T, const int* PA, int* first, int* last, int depth) {
#define STACK_SIZE SS_MISORT_STACKSIZE
    struct {
        int *a, *b, c;
        int d;
    } stack[STACK_SIZE];
    const unsigned char* Td;
    int *a, *b, *c, *d, *e, *f;
    int s, t;
    int ssize;
    int limit;
    int v, x = 0;

    for (ssize = 0, limit = ss_ilg(last - first);;) {
        if ((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
#if 1 < SS_INSERTIONSORT_THRESHOLD
            if (1 < (last - first)) {
                ss_insertionsort(T, PA, first, last, depth);
            }
#endif
            STACK_POP(first, last, depth, limit);
            continue;
        }

        Td = T + depth;
        if (limit-- == 0) {
            ss_heapsort(Td, PA, first, last - first);
        }
        if (limit < 0) {
            for (a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
                if ((x = Td[PA[*a]]) != v) {
                    if (1 < (a - first)) {
                        break;
                    }
                    v = x;
                    first = a;
                }
            }
            if (Td[PA[*first] - 1] < v) {
                first = ss_partition(PA, first, a, depth);
            }
            if ((a - first) <= (last - a)) {
                if (1 < (a - first)) {
                    STACK_PUSH(a, last, depth, -1);
                    last = a, depth += 1, limit = ss_ilg(a - first);
                } else {
                    first = a, limit = -1;
                }
            } else {
                if (1 < (last - a)) {
                    STACK_PUSH(first, a, depth + 1, ss_ilg(a - first));
                    first = a, limit = -1;
                } else {
                    last = a, depth += 1, limit = ss_ilg(a - first);
                }
            }
            continue;
        }

        /* choose pivot */
        a = ss_pivot(Td, PA, first, last);
        v = Td[PA[*a]];
        SWAP(*first, *a);

        /* partition */
        for (b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) {
        }
        if (((a = b) < last) && (x < v)) {
            for (; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
                if (x == v) {
                    SWAP(*b, *a);
                    ++a;
                }
            }
        }
        for (c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) {
        }
        if ((b < (d = c)) && (x > v)) {
            for (; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
                if (x == v) {
                    SWAP(*c, *d);
                    --d;
                }
            }
        }
        for (; b < c;) {
            SWAP(*b, *c);
            for (; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
                if (x == v) {
                    SWAP(*b, *a);
                    ++a;
                }
            }
            for (; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
                if (x == v) {
                    SWAP(*c, *d);
                    --d;
                }
            }
        }

        if (a <= d) {
            c = b - 1;

            if ((s = a - first) > (t = b - a)) {
                s = t;
            }
            for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
                SWAP(*e, *f);
            }
            if ((s = d - c) > (t = last - d - 1)) {
                s = t;
            }
            for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
                SWAP(*e, *f);
            }

            a = first + (b - a), c = last - (d - c);
            b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);

            if ((a - first) <= (last - c)) {
                if ((last - c) <= (c - b)) {
                    STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
                    STACK_PUSH(c, last, depth, limit);
                    last = a;
                } else if ((a - first) <= (c - b)) {
                    STACK_PUSH(c, last, depth, limit);
                    STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
                    last = a;
                } else {
                    STACK_PUSH(c, last, depth, limit);
                    STACK_PUSH(first, a, depth, limit);
                    first = b, last = c, depth += 1, limit = ss_ilg(c - b);
                }
            } else {
                if ((a - first) <= (c - b)) {
                    STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
                    STACK_PUSH(first, a, depth, limit);
                    first = c;
                } else if ((last - c) <= (c - b)) {
                    STACK_PUSH(first, a, depth, limit);
                    STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
                    first = c;
                } else {
                    STACK_PUSH(first, a, depth, limit);
                    STACK_PUSH(c, last, depth, limit);
                    first = b, last = c, depth += 1, limit = ss_ilg(c - b);
                }
            }
        } else {
            limit += 1;
            if (Td[PA[*first] - 1] < v) {
                first = ss_partition(PA, first, last, depth);
                limit = ss_ilg(last - first);
            }
            depth += 1;
        }
    }
#undef STACK_SIZE
}

#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */

/*---------------------------------------------------------------------------*/

#if SS_BLOCKSIZE != 0

static INLINE void ss_blockswap(int* a, int* b, int n) {
    int t;
    for (; 0 < n; --n, ++a, ++b) {
        t = *a, *a = *b, *b = t;
    }
}

static INLINE void ss_rotate(int* first, int* middle, int* last) {
    int *a, *b, t;
    int l, r;
    l = middle - first, r = last - middle;
    for (; (0 < l) && (0 < r);) {
        if (l == r) {
            ss_blockswap(first, middle, l);
            break;
        }
        if (l < r) {
            a = last - 1, b = middle - 1;
            t = *a;
            do {
                *a-- = *b, *b-- = *a;
                if (b < first) {
                    *a = t;
                    last = a;
                    if ((r -= l + 1) <= l) {
                        break;
                    }
                    a -= 1, b = middle - 1;
                    t = *a;
                }
            } while (1);
        } else {
            a = first, b = middle;
            t = *a;
            do {
                *a++ = *b, *b++ = *a;
                if (last <= b) {
                    *a = t;
                    first = a + 1;
                    if ((l -= r + 1) <= r) {
                        break;
                    }
                    a += 1, b = middle;
                    t = *a;
                }
            } while (1);
        }
    }
}

/*---------------------------------------------------------------------------*/

static void ss_inplacemerge(const unsigned char* T, const int* PA, int* first, int* middle, int* last, int depth) {
    const int* p;
    int *a, *b;
    int len, half;
    int q, r;
    int x;

    for (;;) {
        if (*(last - 1) < 0) {
            x = 1;
            p = PA + ~*(last - 1);
        } else {
            x = 0;
            p = PA + *(last - 1);
        }
        for (a = first, len = middle - first, half = len >> 1, r = -1; 0 < len; len = half, half >>= 1) {
            b = a + half;
            q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
            if (q < 0) {
                a = b + 1;
                half -= (len & 1) ^ 1;
            } else {
                r = q;
            }
        }
        if (a < middle) {
            if (r == 0) {
                *a = ~*a;
            }
            ss_rotate(a, middle, last);
            last -= middle - a;
            middle = a;
            if (first == middle) {
                break;
            }
        }
        --last;
        if (x != 0) {
            while (*--last < 0) {
            }
        }
        if (middle == last) {
            break;
        }
    }
}

/*---------------------------------------------------------------------------*/

/* Merge-forward with internal buffer. */
static void
ss_mergeforward(const unsigned char* T, const int* PA, int* first, int* middle, int* last, int* buf, int depth) {
    int *a, *b, *c, *bufend;
    int t;
    int r;

    bufend = buf + (middle - first) - 1;
    ss_blockswap(buf, first, middle - first);

    for (t = *(a = first), b = buf, c = middle;;) {
        r = ss_compare(T, PA + *b, PA + *c, depth);
        if (r < 0) {
            do {
                *a++ = *b;
                if (bufend <= b) {
                    *bufend = t;
                    return;
                }
                *b++ = *a;
            } while (*b < 0);
        } else if (r > 0) {
            do {
                *a++ = *c, *c++ = *a;
                if (last <= c) {
                    while (b < bufend) {
                        *a++ = *b, *b++ = *a;
                    }
                    *a = *b, *b = t;
                    return;
                }
            } while (*c < 0);
        } else {
            *c = ~*c;
            do {
                *a++ = *b;
                if (bufend <= b) {
                    *bufend = t;
                    return;
                }
                *b++ = *a;
            } while (*b < 0);

            do {
                *a++ = *c, *c++ = *a;
                if (last <= c) {
                    while (b < bufend) {
                        *a++ = *b, *b++ = *a;
                    }
                    *a = *b, *b = t;
                    return;
                }
            } while (*c < 0);
        }
    }
}

/* Merge-backward with internal buffer. */
static void
ss_mergebackward(const unsigned char* T, const int* PA, int* first, int* middle, int* last, int* buf, int depth) {
    const int *p1, *p2;
    int *a, *b, *c, *bufend;
    int t;
    int r;
    int x;

    bufend = buf + (last - middle) - 1;
    ss_blockswap(buf, middle, last - middle);

    x = 0;
    if (*bufend < 0) {
        p1 = PA + ~*bufend;
        x |= 1;
    } else {
        p1 = PA + *bufend;
    }
    if (*(middle - 1) < 0) {
        p2 = PA + ~*(middle - 1);
        x |= 2;
    } else {
        p2 = PA + *(middle - 1);
    }
    for (t = *(a = last - 1), b = bufend, c = middle - 1;;) {
        r = ss_compare(T, p1, p2, depth);
        if (0 < r) {
            if (x & 1) {
                do {
                    *a-- = *b, *b-- = *a;
                } while (*b < 0);
                x ^= 1;
            }
            *a-- = *b;
            if (b <= buf) {
                *buf = t;
                break;
            }
            *b-- = *a;
            if (*b < 0) {
                p1 = PA + ~*b;
                x |= 1;
            } else {
                p1 = PA + *b;
            }
        } else if (r < 0) {
            if (x & 2) {
                do {
                    *a-- = *c, *c-- = *a;
                } while (*c < 0);
                x ^= 2;
            }
            *a-- = *c, *c-- = *a;
            if (c < first) {
                while (buf < b) {
                    *a-- = *b, *b-- = *a;
                }
                *a = *b, *b = t;
                break;
            }
            if (*c < 0) {
                p2 = PA + ~*c;
                x |= 2;
            } else {
                p2 = PA + *c;
            }
        } else {
            if (x & 1) {
                do {
                    *a-- = *b, *b-- = *a;
                } while (*b < 0);
                x ^= 1;
            }
            *a-- = ~*b;
            if (b <= buf) {
                *buf = t;
                break;
            }
            *b-- = *a;
            if (x & 2) {
                do {
                    *a-- = *c, *c-- = *a;
                } while (*c < 0);
                x ^= 2;
            }
            *a-- = *c, *c-- = *a;
            if (c < first) {
                while (buf < b) {
                    *a-- = *b, *b-- = *a;
                }
                *a = *b, *b = t;
                break;
            }
            if (*b < 0) {
                p1 = PA + ~*b;
                x |= 1;
            } else {
                p1 = PA + *b;
            }
            if (*c < 0) {
                p2 = PA + ~*c;
                x |= 2;
            } else {
                p2 = PA + *c;
            }
        }
    }
}

/* D&C based merge. */
static void ss_swapmerge(const unsigned char* T,
                         const int* PA,
                         int* first,
                         int* middle,
                         int* last,
                         int* buf,
                         int bufsize,
                         int depth) {
#define STACK_SIZE SS_SMERGE_STACKSIZE
#define GETIDX(a) ((0 <= (a)) ? (a) : (~(a)))
#define MERGE_CHECK(a, b, c)                                                                         \
    do {                                                                                             \
        if (((c)&1) || (((c)&2) && (ss_compare(T, PA + GETIDX(*((a)-1)), PA + *(a), depth) == 0))) { \
            *(a) = ~*(a);                                                                            \
        }                                                                                            \
        if (((c)&4) && ((ss_compare(T, PA + GETIDX(*((b)-1)), PA + *(b), depth) == 0))) {            \
            *(b) = ~*(b);                                                                            \
        }                                                                                            \
    } while (0)
    struct {
        int *a, *b, *c;
        int d;
    } stack[STACK_SIZE];
    int *l, *r, *lm, *rm;
    int m, len, half;
    int ssize;
    int check, next;

    for (check = 0, ssize = 0;;) {
        if ((last - middle) <= bufsize) {
            if ((first < middle) && (middle < last)) {
                ss_mergebackward(T, PA, first, middle, last, buf, depth);
            }
            MERGE_CHECK(first, last, check);
            STACK_POP(first, middle, last, check);
            continue;
        }

        if ((middle - first) <= bufsize) {
            if (first < middle) {
                ss_mergeforward(T, PA, first, middle, last, buf, depth);
            }
            MERGE_CHECK(first, last, check);
            STACK_POP(first, middle, last, check);
            continue;
        }

        for (m = 0, len = MIN(middle - first, last - middle), half = len >> 1; 0 < len; len = half, half >>= 1) {
            if (ss_compare(T, PA + GETIDX(*(middle + m + half)), PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
                m += half + 1;
                half -= (len & 1) ^ 1;
            }
        }

        if (0 < m) {
            lm = middle - m, rm = middle + m;
            ss_blockswap(lm, middle, m);
            l = r = middle, next = 0;
            if (rm < last) {
                if (*rm < 0) {
                    *rm = ~*rm;
                    if (first < lm) {
                        for (; *--l < 0;) {
                        }
                        next |= 4;
                    }
                    next |= 1;
                } else if (first < lm) {
                    for (; *r < 0; ++r) {
                    }
                    next |= 2;
                }
            }

            if ((l - first) <= (last - r)) {
                STACK_PUSH(r, rm, last, (next & 3) | (check & 4));
                middle = lm, last = l, check = (check & 3) | (next & 4);
            } else {
                if ((next & 2) && (r == middle)) {
                    next ^= 6;
                }
                STACK_PUSH(first, lm, l, (check & 3) | (next & 4));
                first = r, middle = rm, check = (next & 3) | (check & 4);
            }
        } else {
            if (ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
                *middle = ~*middle;
            }
            MERGE_CHECK(first, last, check);
            STACK_POP(first, middle, last, check);
        }
    }
#undef STACK_SIZE
}

#endif /* SS_BLOCKSIZE != 0 */

/*---------------------------------------------------------------------------*/

/* Substring sort */
static void sssort(const unsigned char* T,
                   const int* PA,
                   int* first,
                   int* last,
                   int* buf,
                   int bufsize,
                   int depth,
                   int n,
                   int lastsuffix) {
    int* a;
#if SS_BLOCKSIZE != 0
    int *b, *middle, *curbuf;
    int j, k, curbufsize, limit;
#endif
    int i;

    if (lastsuffix != 0) {
        ++first;
    }

#if SS_BLOCKSIZE == 0
    ss_mintrosort(T, PA, first, last, depth);
#else
    if ((bufsize < SS_BLOCKSIZE) && (bufsize < (last - first)) && (bufsize < (limit = ss_isqrt(last - first)))) {
        if (SS_BLOCKSIZE < limit) {
            limit = SS_BLOCKSIZE;
        }
        buf = middle = last - limit, bufsize = limit;
    } else {
        middle = last, limit = 0;
    }
    for (a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) {
#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
        ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
#elif 1 < SS_BLOCKSIZE
        ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
#endif
        curbufsize = last - (a + SS_BLOCKSIZE);
        curbuf = a + SS_BLOCKSIZE;
        if (curbufsize <= bufsize) {
            curbufsize = bufsize, curbuf = buf;
        }
        for (b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) {
            ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
        }
    }
#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
    ss_mintrosort(T, PA, a, middle, depth);
#elif 1 < SS_BLOCKSIZE
    ss_insertionsort(T, PA, a, middle, depth);
#endif
    for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
        if (i & 1) {
            ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
            a -= k;
        }
    }
    if (limit != 0) {
#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
        ss_mintrosort(T, PA, middle, last, depth);
#elif 1 < SS_BLOCKSIZE
        ss_insertionsort(T, PA, middle, last, depth);
#endif
        ss_inplacemerge(T, PA, first, middle, last, depth);
    }
#endif

    if (lastsuffix != 0) {
        /* Insert last type B* suffix. */
        int PAi[2];
        PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
        for (a = first, i = *(first - 1); (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));
             ++a) {
            *(a - 1) = *a;
        }
        *(a - 1) = i;
    }
}

/*---------------------------------------------------------------------------*/

static INLINE int tr_ilg(int n) {
    return (n & 0xffff0000) ? ((n & 0xff000000) ? 24 + lg_table[(n >> 24) & 0xff] : 16 + lg_table[(n >> 16) & 0xff])
                            : ((n & 0x0000ff00) ? 8 + lg_table[(n >> 8) & 0xff] : 0 + lg_table[(n >> 0) & 0xff]);
}

/*---------------------------------------------------------------------------*/

/* Simple insertionsort for small size groups. */
static void tr_insertionsort(const int* ISAd, int* first, int* last) {
    int *a, *b;
    int t, r;

    for (a = first + 1; a < last; ++a) {
        for (t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) {
            do {
                *(b + 1) = *b;
            } while ((first <= --b) && (*b < 0));
            if (b < first) {
                break;
            }
        }
        if (r == 0) {
            *b = ~*b;
        }
        *(b + 1) = t;
    }
}

/*---------------------------------------------------------------------------*/

static INLINE void tr_fixdown(const int* ISAd, int* SA, int i, int size) {
    int j, k;
    int v;
    int c, d, e;

    for (v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
        d = ISAd[SA[k = j++]];
        if (d < (e = ISAd[SA[j]])) {
            k = j;
            d = e;
        }
        if (d <= c) {
            break;
        }
    }
    SA[i] = v;
}

/* Simple top-down heapsort. */
static void tr_heapsort(const int* ISAd, int* SA, int size) {
    int i, m;
    int t;

    m = size;
    if ((size % 2) == 0) {
        m--;
        if (ISAd[SA[m / 2]] < ISAd[SA[m]]) {
            SWAP(SA[m], SA[m / 2]);
        }
    }

    for (i = m / 2 - 1; 0 <= i; --i) {
        tr_fixdown(ISAd, SA, i, m);
    }
    if ((size % 2) == 0) {
        SWAP(SA[0], SA[m]);
        tr_fixdown(ISAd, SA, 0, m);
    }
    for (i = m - 1; 0 < i; --i) {
        t = SA[0], SA[0] = SA[i];
        tr_fixdown(ISAd, SA, 0, i);
        SA[i] = t;
    }
}

/*---------------------------------------------------------------------------*/

/* Returns the median of three elements. */
static INLINE int* tr_median3(const int* ISAd, int* v1, int* v2, int* v3) {
    int* t;
    if (ISAd[*v1] > ISAd[*v2]) {
        SWAP(v1, v2);
    }
    if (ISAd[*v2] > ISAd[*v3]) {
        if (ISAd[*v1] > ISAd[*v3]) {
            return v1;
        } else {
            return v3;
        }
    }
    return v2;
}

/* Returns the median of five elements. */
static INLINE int* tr_median5(const int* ISAd, int* v1, int* v2, int* v3, int* v4, int* v5) {
    int* t;
    if (ISAd[*v2] > ISAd[*v3]) {
        SWAP(v2, v3);
    }
    if (ISAd[*v4] > ISAd[*v5]) {
        SWAP(v4, v5);
    }
    if (ISAd[*v2] > ISAd[*v4]) {
        SWAP(v2, v4);
        SWAP(v3, v5);
    }
    if (ISAd[*v1] > ISAd[*v3]) {
        SWAP(v1, v3);
    }
    if (ISAd[*v1] > ISAd[*v4]) {
        SWAP(v1, v4);
        SWAP(v3, v5);
    }
    if (ISAd[*v3] > ISAd[*v4]) {
        return v4;
    }
    return v3;
}

/* Returns the pivot element. */
static INLINE int* tr_pivot(const int* ISAd, int* first, int* last) {
    int* middle;
    int t;

    t = last - first;
    middle = first + t / 2;

    if (t <= 512) {
        if (t <= 32) {
            return tr_median3(ISAd, first, middle, last - 1);
        } else {
            t >>= 2;
            return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1);
        }
    }
    t >>= 3;
    first = tr_median3(ISAd, first, first + t, first + (t << 1));
    middle = tr_median3(ISAd, middle - t, middle, middle + t);
    last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1);
    return tr_median3(ISAd, first, middle, last);
}

/*---------------------------------------------------------------------------*/

typedef struct _trbudget_t trbudget_t;
struct _trbudget_t {
    int chance;
    int remain;
    int incval;
    int count;
};

static INLINE void trbudget_init(trbudget_t* budget, int chance, int incval) {
    budget->chance = chance;
    budget->remain = budget->incval = incval;
}

static INLINE int trbudget_check(trbudget_t* budget, int size) {
    if (size <= budget->remain) {
        budget->remain -= size;
        return 1;
    }
    if (budget->chance == 0) {
        budget->count += size;
        return 0;
    }
    budget->remain += budget->incval - size;
    budget->chance -= 1;
    return 1;
}

/*---------------------------------------------------------------------------*/

static INLINE void tr_partition(const int* ISAd, int* first, int* middle, int* last, int** pa, int** pb, int v) {
    int *a, *b, *c, *d, *e, *f;
    int t, s;
    int x = 0;

    for (b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) {
    }
    if (((a = b) < last) && (x < v)) {
        for (; (++b < last) && ((x = ISAd[*b]) <= v);) {
            if (x == v) {
                SWAP(*b, *a);
                ++a;
            }
        }
    }
    for (c = last; (b < --c) && ((x = ISAd[*c]) == v);) {
    }
    if ((b < (d = c)) && (x > v)) {
        for (; (b < --c) && ((x = ISAd[*c]) >= v);) {
            if (x == v) {
                SWAP(*c, *d);
                --d;
            }
        }
    }
    for (; b < c;) {
        SWAP(*b, *c);
        for (; (++b < c) && ((x = ISAd[*b]) <= v);) {
            if (x == v) {
                SWAP(*b, *a);
                ++a;
            }
        }
        for (; (b < --c) && ((x = ISAd[*c]) >= v);) {
            if (x == v) {
                SWAP(*c, *d);
                --d;
            }
        }
    }

    if (a <= d) {
        c = b - 1;
        if ((s = a - first) > (t = b - a)) {
            s = t;
        }
        for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
            SWAP(*e, *f);
        }
        if ((s = d - c) > (t = last - d - 1)) {
            s = t;
        }
        for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
            SWAP(*e, *f);
        }
        first += (b - a), last -= (d - c);
    }
    *pa = first, *pb = last;
}

static void tr_copy(int* ISA, const int* SA, int* first, int* a, int* b, int* last, int depth) {
    /* sort suffixes of middle partition
       by using sorted order of suffixes of left and right partition. */
    int *c, *d, *e;
    int s, v;

    v = b - SA - 1;
    for (c = first, d = a - 1; c <= d; ++c) {
        if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
            *++d = s;
            ISA[s] = d - SA;
        }
    }
    for (c = last - 1, e = d + 1, d = b; e < d; --c) {
        if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
            *--d = s;
            ISA[s] = d - SA;
        }
    }
}

static void tr_partialcopy(int* ISA, const int* SA, int* first, int* a, int* b, int* last, int depth) {
    int *c, *d, *e;
    int s, v;
    int rank, lastrank, newrank = -1;

    v = b - SA - 1;
    lastrank = -1;
    for (c = first, d = a - 1; c <= d; ++c) {
        if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
            *++d = s;
            rank = ISA[s + depth];
            if (lastrank != rank) {
                lastrank = rank;
                newrank = d - SA;
            }
            ISA[s] = newrank;
        }
    }

    lastrank = -1;
    for (e = d; first <= e; --e) {
        rank = ISA[*e];
        if (lastrank != rank) {
            lastrank = rank;
            newrank = e - SA;
        }
        if (newrank != rank) {
            ISA[*e] = newrank;
        }
    }

    lastrank = -1;
    for (c = last - 1, e = d + 1, d = b; e < d; --c) {
        if ((0 <= (s = *c - depth)) && (ISA[s] == v)) {
            *--d = s;
            rank = ISA[s + depth];
            if (lastrank != rank) {
                lastrank = rank;
                newrank = d - SA;
            }
            ISA[s] = newrank;
        }
    }
}

static void tr_introsort(int* ISA, const int* ISAd, int* SA, int* first, int* last, trbudget_t* budget) {
#define STACK_SIZE TR_STACKSIZE
    struct {
        const int* a;
        int *b, *c;
        int d, e;
    } stack[STACK_SIZE];
    int *a, *b, *c;
    int t;
    int v, x = 0;
    int incr = ISAd - ISA;
    int limit, next;
    int ssize, trlink = -1;

    for (ssize = 0, limit = tr_ilg(last - first);;) {
        if (limit < 0) {
            if (limit == -1) {
                /* tandem repeat partition */
                tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1);

                /* update ranks */
                if (a < last) {
                    for (c = first, v = a - SA - 1; c < a; ++c) {
                        ISA[*c] = v;
                    }
                }
                if (b < last) {
                    for (c = a, v = b - SA - 1; c < b; ++c) {
                        ISA[*c] = v;
                    }
                }

                /* push */
                if (1 < (b - a)) {
                    STACK_PUSH5(NULL, a, b, 0, 0);
                    STACK_PUSH5(ISAd - incr, first, last, -2, trlink);
                    trlink = ssize - 2;
                }
                if ((a - first) <= (last - b)) {
                    if (1 < (a - first)) {
                        STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink);
                        last = a, limit = tr_ilg(a - first);
                    } else if (1 < (last - b)) {
                        first = b, limit = tr_ilg(last - b);
                    } else {
                        STACK_POP5(ISAd, first, last, limit, trlink);
                    }
                } else {
                    if (1 < (last - b)) {
                        STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink);
                        first = b, limit = tr_ilg(last - b);
                    } else if (1 < (a - first)) {
                        last = a, limit = tr_ilg(a - first);
                    } else {
                        STACK_POP5(ISAd, first, last, limit, trlink);
                    }
                }
            } else if (limit == -2) {
                /* tandem repeat copy */
                a = stack[--ssize].b, b = stack[ssize].c;
                if (stack[ssize].d == 0) {
                    tr_copy(ISA, SA, first, a, b, last, ISAd - ISA);
                } else {
                    if (0 <= trlink) {
                        stack[trlink].d = -1;
                    }
                    tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA);
                }
                STACK_POP5(ISAd, first, last, limit, trlink);
            } else {
                /* sorted partition */
                if (0 <= *first) {
                    a = first;
                    do {
                        ISA[*a] = a - SA;
                    } while ((++a < last) && (0 <= *a));
                    first = a;
                }
                if (first < last) {
                    a = first;
                    do {
                        *a = ~*a;
                    } while (*++a < 0);
                    next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1;
                    if (++a < last) {
                        for (b = first, v = a - SA - 1; b < a; ++b) {
                            ISA[*b] = v;
                        }
                    }

                    /* push */
                    if (trbudget_check(budget, a - first)) {
                        if ((a - first) <= (last - a)) {
                            STACK_PUSH5(ISAd, a, last, -3, trlink);
                            ISAd += incr, last = a, limit = next;
                        } else {
                            if (1 < (last - a)) {
                                STACK_PUSH5(ISAd + incr, first, a, next, trlink);
                                first = a, limit = -3;
                            } else {
                                ISAd += incr, last = a, limit = next;
                            }
                        }
                    } else {
                        if (0 <= trlink) {
                            stack[trlink].d = -1;
                        }
                        if (1 < (last - a)) {
                            first = a, limit = -3;
                        } else {
                            STACK_POP5(ISAd, first, last, limit, trlink);
                        }
                    }
                } else {
                    STACK_POP5(ISAd, first, last, limit, trlink);
                }
            }
            continue;
        }

        if ((last - first) <= TR_INSERTIONSORT_THRESHOLD) {
            tr_insertionsort(ISAd, first, last);
            limit = -3;
            continue;
        }

        if (limit-- == 0) {
            tr_heapsort(ISAd, first, last - first);
            for (a = last - 1; first < a; a = b) {
                for (x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) {
                    *b = ~*b;
                }
            }
            limit = -3;
            continue;
        }

        /* choose pivot */
        a = tr_pivot(ISAd, first, last);
        SWAP(*first, *a);
        v = ISAd[*first];

        /* partition */
        tr_partition(ISAd, first, first + 1, last, &a, &b, v);
        if ((last - first) != (b - a)) {
            next = (ISA[*a] != v) ? tr_ilg(b - a) : -1;

            /* update ranks */
            for (c = first, v = a - SA - 1; c < a; ++c) {
                ISA[*c] = v;
            }
            if (b < last) {
                for (c = a, v = b - SA - 1; c < b; ++c) {
                    ISA[*c] = v;
                }
            }

            /* push */
            if ((1 < (b - a)) && (trbudget_check(budget, b - a))) {
                if ((a - first) <= (last - b)) {
                    if ((last - b) <= (b - a)) {
                        if (1 < (a - first)) {
                            STACK_PUSH5(ISAd + incr, a, b, next, trlink);
                            STACK_PUSH5(ISAd, b, last, limit, trlink);
                            last = a;
                        } else if (1 < (last - b)) {
                            STACK_PUSH5(ISAd + incr, a, b, next, trlink);
                            first = b;
                        } else {
                            ISAd += incr, first = a, last = b, limit = next;
                        }
                    } else if ((a - first) <= (b - a)) {
                        if (1 < (a - first)) {
                            STACK_PUSH5(ISAd, b, last, limit, trlink);
                            STACK_PUSH5(ISAd + incr, a, b, next, trlink);
                            last = a;
                        } else {
                            STACK_PUSH5(ISAd, b, last, limit, trlink);
                            ISAd += incr, first = a, last = b, limit = next;
                        }
                    } else {
                        STACK_PUSH5(ISAd, b, last, limit, trlink);
                        STACK_PUSH5(ISAd, first, a, limit, trlink);
                        ISAd += incr, first = a, last = b, limit = next;
                    }
                } else {
                    if ((a - first) <= (b - a)) {
                        if (1 < (last - b)) {
                            STACK_PUSH5(ISAd + incr, a, b, next, trlink);
                            STACK_PUSH5(ISAd, first, a, limit, trlink);
                            first = b;
                        } else if (1 < (a - first)) {
                            STACK_PUSH5(ISAd + incr, a, b, next, trlink);
                            last = a;
                        } else {
                            ISAd += incr, first = a, last = b, limit = next;
                        }
                    } else if ((last - b) <= (b - a)) {
                        if (1 < (last - b)) {
                            STACK_PUSH5(ISAd, first, a, limit, trlink);
                            STACK_PUSH5(ISAd + incr, a, b, next, trlink);
                            first = b;
                        } else {
                            STACK_PUSH5(ISAd, first, a, limit, trlink);
                            ISAd += incr, first = a, last = b, limit = next;
                        }
                    } else {
                        STACK_PUSH5(ISAd, first, a, limit, trlink);
                        STACK_PUSH5(ISAd, b, last, limit, trlink);
                        ISAd += incr, first = a, last = b, limit = next;
                    }
                }
            } else {
                if ((1 < (b - a)) && (0 <= trlink)) {
                    stack[trlink].d = -1;
                }
                if ((a - first) <= (last - b)) {
                    if (1 < (a - first)) {
                        STACK_PUSH5(ISAd, b, last, limit, trlink);
                        last = a;
                    } else if (1 < (last - b)) {
                        first = b;
                    } else {
                        STACK_POP5(ISAd, first, last, limit, trlink);
                    }
                } else {
                    if (1 < (last - b)) {
                        STACK_PUSH5(ISAd, first, a, limit, trlink);
                        first = b;
                    } else if (1 < (a - first)) {
                        last = a;
                    } else {
                        STACK_POP5(ISAd, first, last, limit, trlink);
                    }
                }
            }
        } else {
            if (trbudget_check(budget, last - first)) {
                limit = tr_ilg(last - first), ISAd += incr;
            } else {
                if (0 <= trlink) {
                    stack[trlink].d = -1;
                }
                STACK_POP5(ISAd, first, last, limit, trlink);
            }
        }
    }
#undef STACK_SIZE
}

/*---------------------------------------------------------------------------*/

/* Tandem repeat sort */
static void trsort(int* ISA, int* SA, int n, int depth) {
    int* ISAd;
    int *first, *last;
    trbudget_t budget;
    int t, skip, unsorted;

    trbudget_init(&budget, tr_ilg(n) * 2 / 3, n);
    /*  trbudget_init(&budget, tr_ilg(n) * 3 / 4, n); */
    for (ISAd = ISA + depth; - n < *SA; ISAd += ISAd - ISA) {
        first = SA;
        skip = 0;
        unsorted = 0;
        do {
            if ((t = *first) < 0) {
                first -= t;
                skip += t;
            } else {
                if (skip != 0) {
                    *(first + skip) = skip;
                    skip = 0;
                }
                last = SA + ISA[t] + 1;
                if (1 < (last - first)) {
                    budget.count = 0;
                    tr_introsort(ISA, ISAd, SA, first, last, &budget);
                    if (budget.count != 0) {
                        unsorted += budget.count;
                    } else {
                        skip = first - last;
                    }
                } else if ((last - first) == 1) {
                    skip = -1;
                }
                first = last;
            }
        } while (first < (SA + n));
        if (skip != 0) {
            *(first + skip) = skip;
        }
        if (unsorted == 0) {
            break;
        }
    }
}

/*---------------------------------------------------------------------------*/

/* Sorts suffixes of type B*. */
static int sort_typeBstar(const unsigned char* T, int* SA, int* bucket_A, int* bucket_B, int n, int openMP) {
    int *PAb, *ISAb, *buf;
#ifdef LIBBSC_OPENMP
    int* curbuf;
    int l;
#endif
    int i, j, k, t, m, bufsize;
    int c0, c1;
#ifdef LIBBSC_OPENMP
    int d0, d1;
#endif
    (void)openMP;

    /* Initialize bucket arrays. */
    for (i = 0; i < BUCKET_A_SIZE; ++i) {
        bucket_A[i] = 0;
    }
    for (i = 0; i < BUCKET_B_SIZE; ++i) {
        bucket_B[i] = 0;
    }

    /* Count the number of occurrences of the first one or two characters of each
       type A, B and B* suffix. Moreover, store the beginning position of all
       type B* suffixes into the array SA. */
    for (i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) {
        /* type A suffix. */
        do {
            ++BUCKET_A(c1 = c0);
        } while ((0 <= --i) && ((c0 = T[i]) >= c1));
        if (0 <= i) {
            /* type B* suffix. */
            ++BUCKET_BSTAR(c0, c1);
            SA[--m] = i;
            /* type B suffix. */
            for (--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
                ++BUCKET_B(c0, c1);
            }
        }
    }
    m = n - m;
    /*
    note:
      A type B* suffix is lexicographically smaller than a type B suffix that
      begins with the same first two characters.
    */

    /* Calculate the index of start/end point of each bucket. */
    for (c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) {
        t = i + BUCKET_A(c0);
        BUCKET_A(c0) = i + j; /* start point */
        i = t + BUCKET_B(c0, c0);
        for (c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) {
            j += BUCKET_BSTAR(c0, c1);
            BUCKET_BSTAR(c0, c1) = j; /* end point */
            i += BUCKET_B(c0, c1);
        }
    }

    if (0 < m) {
        /* Sort the type B* suffixes by their first two characters. */
        PAb = SA + n - m;
        ISAb = SA + m;
        for (i = m - 2; 0 <= i; --i) {
            t = PAb[i], c0 = T[t], c1 = T[t + 1];
            SA[--BUCKET_BSTAR(c0, c1)] = i;
        }
        t = PAb[m - 1], c0 = T[t], c1 = T[t + 1];
        SA[--BUCKET_BSTAR(c0, c1)] = m - 1;

        /* Sort the type B* substrings using sssort. */
#ifdef LIBBSC_OPENMP
        if (openMP) {
            buf = SA + m;
            c0 = ALPHABET_SIZE - 2, c1 = ALPHABET_SIZE - 1, j = m;
#pragma omp parallel default(shared) private(bufsize, curbuf, k, l, d0, d1)
            {
                bufsize = (n - (2 * m)) / omp_get_num_threads();
                curbuf = buf + omp_get_thread_num() * bufsize;
                k = 0;
                for (;;) {
#pragma omp critical(sssort_lock)
                    {
                        if (0 < (l = j)) {
                            d0 = c0, d1 = c1;
                            do {
                                k = BUCKET_BSTAR(d0, d1);
                                if (--d1 <= d0) {
                                    d1 = ALPHABET_SIZE - 1;
                                    if (--d0 < 0) {
                                        break;
                                    }
                                }
                            } while (((l - k) <= 1) && (0 < (l = k)));
                            c0 = d0, c1 = d1, j = k;
                        }
                    }
                    if (l == 0) {
                        break;
                    }
                    sssort(T, PAb, SA + k, SA + l, curbuf, bufsize, 2, n, *(SA + k) == (m - 1));
                }
            }
        } else {
            buf = SA + m, bufsize = n - (2 * m);
            for (c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
                for (c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
                    i = BUCKET_BSTAR(c0, c1);
                    if (1 < (j - i)) {
                        sssort(T, PAb, SA + i, SA + j, buf, bufsize, 2, n, *(SA + i) == (m - 1));
                    }
                }
            }
        }
#else
        buf = SA + m, bufsize = n - (2 * m);
        for (c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
            for (c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
                i = BUCKET_BSTAR(c0, c1);
                if (1 < (j - i)) {
                    sssort(T, PAb, SA + i, SA + j, buf, bufsize, 2, n, *(SA + i) == (m - 1));
                }
            }
        }
#endif

        /* Compute ranks of type B* substrings. */
        for (i = m - 1; 0 <= i; --i) {
            if (0 <= SA[i]) {
                j = i;
                do {
                    ISAb[SA[i]] = i;
                } while ((0 <= --i) && (0 <= SA[i]));
                SA[i + 1] = i - j;
                if (i <= 0) {
                    break;
                }
            }
            j = i;
            do {
                ISAb[SA[i] = ~SA[i]] = j;
            } while (SA[--i] < 0);
            ISAb[SA[i]] = j;
        }

        /* Construct the inverse suffix array of type B* suffixes using trsort. */
        trsort(ISAb, SA, m, 1);

        /* Set the sorted order of tyoe B* suffixes. */
        for (i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) {
            for (--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) {
            }
            if (0 <= i) {
                t = i;
                for (--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
                }
                SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t;
            }
        }

        /* Calculate the index of start/end point of each bucket. */
        BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */
        for (c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) {
            i = BUCKET_A(c0 + 1) - 1;
            for (c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) {
                t = i - BUCKET_B(c0, c1);
                BUCKET_B(c0, c1) = i; /* end point */

                /* Move all type B* suffixes to the correct position. */
                for (i = t, j = BUCKET_BSTAR(c0, c1); j <= k; --i, --k) {
                    SA[i] = SA[k];
                }
            }
            BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */
            BUCKET_B(c0, c0) = i;                                /* end point */
        }
    }

    return m;
}

/* Constructs the suffix array by using the sorted order of type B* suffixes. */
static void construct_SA(const unsigned char* T, int* SA, int* bucket_A, int* bucket_B, int n, int m) {
    int *i, *j, *k;
    int s;
    int c0, c1, c2;

    if (0 < m) {
        /* Construct the sorted order of type B suffixes by using
           the sorted order of type B* suffixes. */
        for (c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
            /* Scan the suffix array from right to left. */
            for (i = SA + BUCKET_BSTAR(c1, c1 + 1), j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; i <= j; --j) {
                if (0 < (s = *j)) {
                    assert(T[s] == c1);
                    assert(((s + 1) < n) && (T[s] <= T[s + 1]));
                    assert(T[s - 1] <= T[s]);
                    *j = ~s;
                    c0 = T[--s];
                    if ((0 < s) && (T[s - 1] > c0)) {
                        s = ~s;
                    }
                    if (c0 != c2) {
                        if (0 <= c2) {
                            BUCKET_B(c2, c1) = k - SA;
                        }
                        k = SA + BUCKET_B(c2 = c0, c1);
                    }
                    assert(k < j);
                    assert(k != NULL);
                    *k-- = s;
                } else {
                    assert(((s == 0) && (T[s] == c1)) || (s < 0));
                    *j = ~s;
                }
            }
        }
    }

    /* Construct the suffix array by using
       the sorted order of type B suffixes. */
    k = SA + BUCKET_A(c2 = T[n - 1]);
    *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1);
    /* Scan the suffix array from left to right. */
    for (i = SA, j = SA + n; i < j; ++i) {
        if (0 < (s = *i)) {
            assert(T[s - 1] >= T[s]);
            c0 = T[--s];
            if ((s == 0) || (T[s - 1] < c0)) {
                s = ~s;
            }
            if (c0 != c2) {
                BUCKET_A(c2) = k - SA;
                k = SA + BUCKET_A(c2 = c0);
            }
            assert(i < k);
            *k++ = s;
        } else {
            assert(s < 0);
            *i = ~s;
        }
    }
}

/* Constructs the burrows-wheeler transformed string directly
   by using the sorted order of type B* suffixes. */
static int construct_BWT(const unsigned char* T, int* SA, int* bucket_A, int* bucket_B, int n, int m) {
    int *i, *j, *k, *orig;
    int s;
    int c0, c1, c2;

    if (0 < m) {
        /* Construct the sorted order of type B suffixes by using
           the sorted order of type B* suffixes. */
        for (c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
            /* Scan the suffix array from right to left. */
            for (i = SA + BUCKET_BSTAR(c1, c1 + 1), j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; i <= j; --j) {
                if (0 < (s = *j)) {
                    assert(T[s] == c1);
                    assert(((s + 1) < n) && (T[s] <= T[s + 1]));
                    assert(T[s - 1] <= T[s]);
                    c0 = T[--s];
                    *j = ~((int)c0);
                    if ((0 < s) && (T[s - 1] > c0)) {
                        s = ~s;
                    }
                    if (c0 != c2) {
                        if (0 <= c2) {
                            BUCKET_B(c2, c1) = k - SA;
                        }
                        k = SA + BUCKET_B(c2 = c0, c1);
                    }
                    assert(k < j);
                    assert(k != NULL);
                    *k-- = s;
                } else if (s != 0) {
                    *j = ~s;
#ifndef NDEBUG
                } else {
                    assert(T[s] == c1);
#endif
                }
            }
        }
    }

    /* Construct the BWTed string by using
       the sorted order of type B suffixes. */
    k = SA + BUCKET_A(c2 = T[n - 1]);
    *k++ = (T[n - 2] < c2) ? ~((int)T[n - 2]) : (n - 1);
    /* Scan the suffix array from left to right. */
    for (i = SA, j = SA + n, orig = SA; i < j; ++i) {
        if (0 < (s = *i)) {
            assert(T[s - 1] >= T[s]);
            c0 = T[--s];
            *i = c0;
            if ((0 < s) && (T[s - 1] < c0)) {
                s = ~((int)T[s - 1]);
            }
            if (c0 != c2) {
                BUCKET_A(c2) = k - SA;
                k = SA + BUCKET_A(c2 = c0);
            }
            assert(i < k);
            *k++ = s;
        } else if (s != 0) {
            *i = ~s;
        } else {
            orig = i;
        }
    }

    return orig - SA;
}

/* Constructs the burrows-wheeler transformed string directly
   by using the sorted order of type B* suffixes. */
static int construct_BWT_indexes(const unsigned char* T,
                                 int* SA,
                                 int* bucket_A,
                                 int* bucket_B,
                                 int n,
                                 int m,
                                 unsigned char* num_indexes,
                                 int* indexes) {
    int *i, *j, *k, *orig;
    int s;
    int c0, c1, c2;

    int mod = n / 8;
    {
        mod |= mod >> 1;
        mod |= mod >> 2;
        mod |= mod >> 4;
        mod |= mod >> 8;
        mod |= mod >> 16;
        mod >>= 1;

        *num_indexes = (unsigned char)((n - 1) / (mod + 1));
    }

    if (0 < m) {
        /* Construct the sorted order of type B suffixes by using
           the sorted order of type B* suffixes. */
        for (c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
            /* Scan the suffix array from right to left. */
            for (i = SA + BUCKET_BSTAR(c1, c1 + 1), j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; i <= j; --j) {
                if (0 < (s = *j)) {
                    assert(T[s] == c1);
                    assert(((s + 1) < n) && (T[s] <= T[s + 1]));
                    assert(T[s - 1] <= T[s]);

                    if ((s & mod) == 0)
                        indexes[s / (mod + 1) - 1] = j - SA;

                    c0 = T[--s];
                    *j = ~((int)c0);
                    if ((0 < s) && (T[s - 1] > c0)) {
                        s = ~s;
                    }
                    if (c0 != c2) {
                        if (0 <= c2) {
                            BUCKET_B(c2, c1) = k - SA;
                        }
                        k = SA + BUCKET_B(c2 = c0, c1);
                    }
                    assert(k < j);
                    assert(k != NULL);
                    *k-- = s;
                } else if (s != 0) {
                    *j = ~s;
#ifndef NDEBUG
                } else {
                    assert(T[s] == c1);
#endif
                }
            }
        }
    }

    /* Construct the BWTed string by using
       the sorted order of type B suffixes. */
    k = SA + BUCKET_A(c2 = T[n - 1]);
    if (T[n - 2] < c2) {
        if (((n - 1) & mod) == 0)
            indexes[(n - 1) / (mod + 1) - 1] = k - SA;
        *k++ = ~((int)T[n - 2]);
    } else {
        *k++ = n - 1;
    }

    /* Scan the suffix array from left to right. */
    for (i = SA, j = SA + n, orig = SA; i < j; ++i) {
        if (0 < (s = *i)) {
            assert(T[s - 1] >= T[s]);

            if ((s & mod) == 0)
                indexes[s / (mod + 1) - 1] = i - SA;

            c0 = T[--s];
            *i = c0;
            if (c0 != c2) {
                BUCKET_A(c2) = k - SA;
                k = SA + BUCKET_A(c2 = c0);
            }
            assert(i < k);
            if ((0 < s) && (T[s - 1] < c0)) {
                if ((s & mod) == 0)
                    indexes[s / (mod + 1) - 1] = k - SA;
                *k++ = ~((int)T[s - 1]);
            } else
                *k++ = s;
        } else if (s != 0) {
            *i = ~s;
        } else {
            orig = i;
        }
    }

    return orig - SA;
}

/*---------------------------------------------------------------------------*/

/*- Function -*/

int divsufsort(const unsigned char* T, int* SA, int n, int openMP) {
    int *bucket_A, *bucket_B;
    int m;
    int err = 0;

    /* Check arguments. */
    if ((T == NULL) || (SA == NULL) || (n < 0)) {
        return -1;
    } else if (n == 0) {
        return 0;
    } else if (n == 1) {
        SA[0] = 0;
        return 0;
    } else if (n == 2) {
        m = (T[0] < T[1]);
        SA[m ^ 1] = 0, SA[m] = 1;
        return 0;
    }

    bucket_A = (int*)malloc(BUCKET_A_SIZE * sizeof(int));
    bucket_B = (int*)malloc(BUCKET_B_SIZE * sizeof(int));

    /* Suffixsort. */
    if ((bucket_A != NULL) && (bucket_B != NULL)) {
        m = sort_typeBstar(T, SA, bucket_A, bucket_B, n, openMP);
        construct_SA(T, SA, bucket_A, bucket_B, n, m);
    } else {
        err = -2;
    }

    free(bucket_B);
    free(bucket_A);

    return err;
}

int divbwt(const unsigned char* T,
           unsigned char* U,
           int* A,
           int n,
           unsigned char* num_indexes,
           int* indexes,
           int openMP) {
    int* B;
    int *bucket_A, *bucket_B;
    int m, pidx, i;

    /* Check arguments. */
    if ((T == NULL) || (U == NULL) || (n < 0)) {
        return -1;
    } else if (n <= 1) {
        if (n == 1) {
            U[0] = T[0];
        }
        return n;
    }

    if ((B = A) == NULL) {
        B = (int*)malloc((size_t)(n + 1) * sizeof(int));
    }
    bucket_A = (int*)malloc(BUCKET_A_SIZE * sizeof(int));
    bucket_B = (int*)malloc(BUCKET_B_SIZE * sizeof(int));

    /* Burrows-Wheeler Transform. */
    if ((B != NULL) && (bucket_A != NULL) && (bucket_B != NULL)) {
        m = sort_typeBstar(T, B, bucket_A, bucket_B, n, openMP);

        if (num_indexes == NULL || indexes == NULL) {
            pidx = construct_BWT(T, B, bucket_A, bucket_B, n, m);
        } else {
            pidx = construct_BWT_indexes(T, B, bucket_A, bucket_B, n, m, num_indexes, indexes);
        }

        /* Copy to output string. */
        U[0] = T[n - 1];
        for (i = 0; i < pidx; ++i) {
            U[i + 1] = (unsigned char)B[i];
        }
        for (i += 1; i < n; ++i) {
            U[i] = (unsigned char)B[i];
        }
        pidx += 1;
    } else {
        pidx = -2;
    }

    free(bucket_B);
    free(bucket_A);
    if (A == NULL) {
        free(B);
    }

    return pidx;
}
